package com.squirrel.michale;

import java.util.*;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/12 10:26 AM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode1202 {


    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {

        if (s.length() == 0) {
            return s;
        }

        char[] chars = s.toCharArray();

        List<Character> characterList = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            characterList.add(chars[i]);
        }

        int len = s.length();
        List<Integer> integerList  = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            integerList.add(i);
        }

        UnionFind<Integer> unionFind = new UnionFind<>(integerList);

        for (List<Integer> pair : pairs) {
            int index1 = pair.get(0);
            int index2 = pair.get(1);
            unionFind.union(index1, index2);
        }

        char[] charArray = s.toCharArray();
        // key：连通分量的代表元，value：同一个连通分量的字符集合（保存在一个优先队列中）
        Map<Integer, PriorityQueue<Character>> hashMap = new HashMap<>(len);
        for (int i = 0; i < len; i++) {
            int root = unionFind.findFather(unionFind.nodes.get(i)).value;
            if (hashMap.containsKey(root)) {
                hashMap.get(root).offer(charArray[i]);
            } else {
                PriorityQueue<Character> minHeap = new PriorityQueue<>();
                minHeap.offer(charArray[i]);
                hashMap.put(root, minHeap);
            }
        }

        // 第 3 步：重组字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < len; i++) {
            int root = unionFind.findFather(unionFind.nodes.get(i)).value;
            stringBuilder.append(hashMap.get(root).poll());
        }
        return stringBuilder.toString();



    }


    public static void main(String[] args) {
        String s = "dcab";
        List<List<Integer>> pairs = new ArrayList<>(new ArrayList<>());
        List<Integer> integerList1 = new ArrayList<>();
        integerList1.add(0);
        integerList1.add(3);
        pairs.add(integerList1);


        List<Integer> integerList2 = new ArrayList<>();
        integerList2.add(1);
        integerList2.add(2);
        pairs.add(integerList2);



        LeetCode1202 leetCode1202 = new LeetCode1202();
        System.out.println(leetCode1202.smallestStringWithSwaps(s, pairs));


    }


    public static class Node<V> {
        V value;

        public Node(V v) {
            value = v;
        }
    }

    public static class UnionFind<V> {
        public HashMap<V, Node<V>> nodes;
        public HashMap<Node<V>, Node<V>> parents;
        public HashMap<Node<V>, Integer> sizeMap;

        public UnionFind(List<V> values) {
            nodes = new HashMap<>();
            parents = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V cur : values) {
                Node<V> node = new Node<>(cur);
                nodes.put(cur, node);
                parents.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        // 给你一个节点，请你往上到不能再往上，把代表返回
        public Node<V> findFather(Node<V> cur) {
            Stack<Node<V>> path = new Stack<>();
            while (cur != parents.get(cur)) {
                path.push(cur);
                cur = parents.get(cur);
            }
            while (!path.isEmpty()) {
                parents.put(path.pop(), cur);
            }
            return cur;
        }

        public boolean isSameSet(V a, V b) {
            return findFather(nodes.get(a)) == findFather(nodes.get(b));
        }

        public void union(V a, V b) {
            Node<V> aHead = findFather(nodes.get(a));
            Node<V> bHead = findFather(nodes.get(b));
            if (aHead != bHead) {
                int aSetSize = sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
                Node<V> small = big == aHead ? bHead : aHead;
                parents.put(small, big);
                sizeMap.put(big, aSetSize + bSetSize);
                sizeMap.remove(small);
            }
        }

        public int sets() {
            return sizeMap.size();
        }

    }


}
